package array.SpiralArray;

/**
 * 题目:给你一个正整数 n ，生成一个包含 1 到 n2 所有元素，且元素按顺时针顺序螺旋排列的 n x n 正方形矩阵 matrix 。
      示例 1：
        输入：n = 3
        输出：[[1,2,3],[8,9,4],[7,6,5]]

 * 循环圈数: 如果是偶数的话循环n/2圈，
           如果是奇数的话，循环n/2还遗漏下最中间的一个数字，此时需要单独对最中间的进行赋值

 * 单边赋值规则: 左闭右开(循环不变量原则:每一条边的处理规则要统一)
 * 定义七个变量: startX(每一圈的起始点x),starty(每一圈的起始点y),
               offset(每次的边界),count(矩阵中需要填写的数字),
               j 代表列, i 代表行，loop(循环圈数);
 * 时间复杂度 O(n^2)
 * 空间复杂度 O(1)
 */

/**
 * 模拟顺时针画矩阵的过程:
 *   填充上行从左到右
 *   填充右列从上到下
 *   填充下行从右到左
 *   填充左列从下到上
 *   由外向内一圈一圈这么画下去。
 */
public class spiralArray {
    public int[][] generateMatrix(int n) {
        int[][] nums = new int[n][n];
        int startX = 0, startY = 0;  // 每一圈的起始点
        int offset = 1;
        int count = 1;  // 矩阵中需要填写的数字
        int loop = 1; // 记录当前的圈数
        int i, j; // j 代表列, i 代表行;

        while (loop <= n / 2) {

            // 顶部
            // 左闭右开，所以判断循环结束时， j 不能等于 n - offset
            for (j = startY; j < n - offset; j++) {
                nums[startX][j] = count++;
            }

            // 右列
            // 左闭右开，所以判断循环结束时， i 不能等于 n - offset
            for (i = startX; i < n - offset; i++) {
                nums[i][j] = count++;
            }

            // 底部
            // 左闭右开，所以判断循环结束时， j != startY
            for (; j > startY; j--) {
                nums[i][j] = count++;
            }

            // 左列
            // 左闭右开，所以判断循环结束时， i != startX
            for (; i > startX; i--) {
                nums[i][j] = count++;
            }
            startX++;
            startY++;
            offset++;
            loop++;
        }
        if (n % 2 == 1) { // n 为奇数时，单独处理矩阵中心的值
            nums[startX][startY] = count;
        }
        return nums;
    }
}

